The invention relates to technology for implementing electronic design automation tools, and in particular embodiments, for performing extraction and recognition of polygons for electronic design automation tools that operate upon an integrated circuit (“IC”) design.
An IC is a small electronic device typically formed from semiconductor material. Each IC contains a large number of electronic components, e.g., transistors, that are wired together to create a self-contained circuit device. The components and wiring on the IC are materialized as a set of geometric shapes or polygons that are placed and routed on the chip material. During placement, the location and positioning of each geometric shape corresponding to an IC component are identified on the IC layers. During routing, a set of routes are identified to tie together the geometric shapes for the electronic components.
Once the layout is finished, it is verified to make sure it satisfies the design rules, which are typically provided by the foundry that is to manufacture the IC device. This verification process is called Design Rule Check (DRC). The design rules are a set of rules regarding minimum distances, sizes, enclosure criteria, among other constraints for implementing the layout. The rules have to be observed in order to maximize chances of a successful fabrication of the integrated circuit.
Numerous other types of operations and analysis may also be performed upon the set of polygons that form the IC design. For example, the polygons may be analyzed to determine whether optical proximity correction (“OPC”) should be applied to the polygons. OPC refers to the process of adding additional polygons to the IC mask design to correct for any anticipated optical effects that may exist to cause errors or inaccuracies in the shapes of components of the final integrated circuit product that are caused by the lithographic process of forming the integrated circuit. A common example of an OPC operation is to analyze the IC design to determine whether there exists polygons having a segment or wall that is not near enough another polygon, which could result as a curved segment in the final IC product due to optical effects of the lithographic process. To correct for this type of optical effect, a scattering bar, below the resolution limit of the lithography equipment, is added parallel to the segment of interest. This scattering bar will cause the lithography equipment to produce a straighter segment or wall for the polygon.
Given the large numbers of components in a typical IC design, it often takes a long period of time and a significant amount of system resources (both for CPU and memory) to perform a set of operations or analysis upon a given IC design. In particular, consider an IC design having many millions of polygons. Each of the polygons potentially need to be analyzed and operated upon to determine, for example, the applicability of scattering bars. As another example, each of the millions of polygons need to be checked to determine and identify any violations of DRC rules.
As the complexity and size of layout data grow dramatically for new generation of Integrated Circuits (IC), existing methods to organize the IC data become ever more inadequate to allow efficient access and analysis of the data.
Therefore, to address this and other problems with the prior solutions, embodiments of the present invention provide an improved approach for organizing, analyzing, and operating upon polygon data which significantly reduces the amount of data required for processing while keeping elements non-interfacing with each other. According to one embodiment, clusters of elements are extracted which are then handled separately. In some embodiments, a set of polygons forms a cluster if for any two polygons from the set of polygons there exists a sequence of polygons from the set such that the distance between any sequential polygons are less than or equal to a given threshold number. Rather than analyzing each and every polygon in the design, repetitive unique patterns are analyzed once, which are then replicated for all clusters which have the same repetitive pattern. Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory, and are not intended to be limiting as to the scope of the invention.